package com.atguigu.structures;


/**
 * f==最后一个值
 * 循环过程中：
 * l永远指向比f小的前一个
 * r永远指向比f大的后一个
 * 当r遇到比小的值时l+1与r交换元素位置
 *
 * 循环结束后最终交换r与l+1的位置
 */
public class QuickSortExample {
    public static void main(String[] args) {
        int[] array = {2,8,7,1,3,5,4,6};
        quickSort(array, 0, 7);
        for (int j : array) {
            System.out.println(j);
        }
    }

    // T(N) = 2 * T(N/2) + O(N)
    // O(NlogN)
    // 退化为下面
    // T(N) = T(N - 1) + O(N)
    // O(N^2)
    public static void quickSort(int[] array, int start, int end) {
        if (start < end) {
            int q = partition(array, start, end); // O(N)
            quickSort(array, start, q - 1); // T(N/2)
            quickSort(array, q + 1, end); // T(N/2)
        }
    }

    public static int partition(int[] array, int start, int end) {
        int r = array[end];
        int i = start - 1;
        for (int j = start; j < end; j++) {
            if (array[j] <= r) {
                i = i + 1;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, r);
        return i + 1;
    }

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
